package main

import (
	"bufio"
	"errors"
	"flag"
	"fmt"
	"math"
	"math/rand"
	"os"
	"regexp"
	"strconv"
	"strings"
	"time"
	"sort"
)

type lineInfo struct {
	lineNO uint
	value  float64
}

type lines []lineInfo

func (l lines) Len() int {
	return len(l)
}

func (l lines) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}

func (l lines) Less(i, j int) bool {
	return l[i].value > l[j].value
}

//used for save the global test information
type gaConfig struct {
	programe        string
	loes, lofs      []int
	nots, noes, nof int
	casesPass       [][]uint64
	casesFailed     [][]uint64
	onesFromPass    []int
	onesFromFailed  []int
	compareValue    lines
}

var dataFilePath *string
var config *gaConfig

//called when loaded the package
func init() {
	dataFilePath = flag.String("file", "compressed_coverage_matrix.txt", "Use -file <filesource>")
}

//init global test configuration
func initConfig(filepath string) (config *gaConfig, err error) {

	defer func() {
		if e := recover(); e != nil {
			fmt.Println(e)
			err = errors.New("resolve cofiguration error")
		}
	}()

	config = new(gaConfig)

	inputFile, err := os.Open(filepath)
	if err != nil {
		panic("读取数据文件失败")
	}
	defer inputFile.Close()

	scanner := bufio.NewScanner(inputFile)

	//regex for extract massive test case data
	re := regexp.MustCompile(`#CASE#(\d{5})#R(\d{1})# ([\d,\s]*)`)

	Loop:
	for {
		scanner.Scan()
		v := strings.Split(scanner.Text(), " ")
		switch v[0] {
		case "#Ver_#":
			config.programe = v[1]
		case "#NOTS#":
			config.nots, err = strconv.Atoi(v[1])
		case "#LOES#":
			config.loes = make([]int, len(v) - 1)
			for i, s := range v[1:] {
				config.loes[i], err = strconv.Atoi(s)
			}
		case "#NOES#":
			config.noes, err = strconv.Atoi(v[1])
			config.onesFromPass = make([]int, config.noes)
			config.onesFromFailed = make([]int, config.noes)
		case "#NOF_#":
			config.nof, err = strconv.Atoi(v[1])
		case "#LOFS#":
			config.lofs = make([]int, len(v) - 1)
			for i, s := range v[1:] {
				config.lofs[i], err = strconv.Atoi(s)
			}
		default:
			submatches := re.FindStringSubmatch(scanner.Text())
			if submatches == nil || len(submatches) < 4 {
				break Loop
			} else if submatches[2] == "1" {
				// displayByteArray(&Record{stringToByteArray(submatches[3], config.noes), 0}, config.noes, config.lofs)
				//fmt.Println(submatches[3])
				config.casesFailed = append(config.casesFailed, stringToByteArray(submatches[3], config, false))
			} else if submatches[2] == "0" {
				//fmt.Println(submatches[3])
				// displayByteArray(&Record{stringToByteArray(submatches[3], config.noes), 0}, config.noes, config.lofs)
				config.casesPass = append(config.casesPass, stringToByteArray(submatches[3], config, true))
			}
		}
	}

	config.compareValue = make(lines, config.noes)
	if (len(config.casesFailed) > 0 && len(config.casesPass) > 0) {
		for i := 0; i < config.noes; i++ {
			//fmt.Println(i, " ", config.onesFromFailed[i], " ", float64(config.noes), " ",float64(config.onesFromPass[i]), " ", float64(len(config.onesFromPass)), " ",float64(config.onesFromFailed[i]) / float64(len(config.casesFailed)),  " ", " ")
			config.compareValue[i].lineNO = uint(i)
			if (config.onesFromPass[i] == 0 && config.onesFromFailed[i] == 0) {
				config.compareValue[i].value = 0;
			} else {
				// Using Tarantula
				//config.compareValue[i].value = float64(config.onesFromFailed[i]) / float64(config.noes) / (float64(config.onesFromPass[i]) / float64(len(config.onesFromPass)) + float64(config.onesFromFailed[i]) / float64(len(config.casesFailed)))
				// using Ochiai
				config.compareValue[i].value = float64(config.onesFromFailed[i]) / math.Sqrt(float64(len(config.casesFailed)) * (float64(config.onesFromFailed[i]) + float64(config.onesFromPass[i])));
			}
		}
	}

	return config, nil
}

//generate random uint64 number cause go doesn't support this
func randomUint64() uint64 {
	return uint64(rand.Int63() << 1 | rand.Int63n(2))
}

//generate random []uint64 with fix size
func randomParent(size int) []uint64 {
	rand.Seed(time.Now().UnixNano())
	var result []uint64

	for i := 0; i < size / 64; i++ {
		result = append(result, randomUint64())
	}

	if size % 64 > 0 {
		appendix := randomUint64()
		offset := uint(64 - (size % 64))
		appendix = (appendix << offset) >> offset
		result = append([]uint64{appendix}, result...)
	}

	return result
}

func haveSex(father []uint64, mother []uint64, fixSize int) (son []uint64, girl []uint64) {
	son = make([]uint64, len(father))
	girl = make([]uint64, len(father))
	for i := 0; i < len(father); i++ {
		//inhert from father
		son[i] = father[i]
		girl[i] = mother[i]
		//different parents
		if (father[i] ^ mother[i]) > 0 {
			//iter to find the different pos
			for pos := uint64(1); pos > 0; pos <<= 1 {
				//found pos
				if ((father[i] ^ mother[i]) & pos) > 0 {
					// fmt.Printf("%065s\n", strconv.FormatUint(pos, 2))
					if rand.Intn(100) < 70 {
						son[i] ^= pos
						girl[i] ^= pos
					}
				}
			}
			// fmt.Println("")
		}
	}

	//mutate for 5% chance
	for i := 0; i < 3; i++{
		var randomFactor uint = uint(rand.Intn(fixSize))
		var mutatePos = uint(len(son)) - 1 - (randomFactor >> 6)
		var mutateFactor = uint64(1 << (randomFactor % 64))
		son[mutatePos] ^= mutateFactor

		randomFactor = uint(rand.Intn(fixSize))
		mutatePos = uint(len(son)) - 1 - (randomFactor >> 6)
		mutateFactor = uint64(1 << (randomFactor % 64))
		girl[mutatePos] ^= mutateFactor
	}

	return son, girl
}

func fitness1(r []uint64, size int, casesSuccess [][]uint64, casesFailed [][]uint64) (fitValue float64) {
	fx := 0.0
	px := 0.0
	fx = fx + 1
	px = px + 1
	for i := 0;i < config.noes;i++ {
		pos := i
		if config.noes % 64 != 0 {
			pos += 64 - config.noes % 64
		}
		found := r[pos / 64] & (1 << uint(63 - (pos % 64)))
		if found > 0{
			fx += float64(config.onesFromFailed[i]) / float64(len(config.casesFailed))
			px += float64(config.onesFromPass[i]) / float64(len(config.casesPass))
		}
	}
	fitValue = float64(1 + fx) / float64(1.0 + fx + px)

	return
}

//calculate the fitness value for one record
func fitness(r []uint64, size int, casesSuccess [][]uint64, casesFailed [][]uint64) (fitValue float64) {

	numOfOnesFromPassCases := 0
	for i := 0; i < len(casesSuccess); i++ {
		for j := 0; j < len(r); j++ {
			buffer := r[j] & casesSuccess[i][j]
			// fmt.Println(i, j, r, casesSuccess[i], buffer)
			for buffer > 0 {
				numOfOnesFromPassCases++
				buffer = buffer & (buffer - 1)
			}
		}
	}

	numOfOnesFromFailedCases := 0
	coverFailedCases := 0
	for i := 0; i < len(casesFailed); i++ {
		cover := false
		for j := 0; j < len(r); j++ {
			buffer := r[j] & casesFailed[i][j]
			if buffer > 0 {
				numOfOnesFromFailedCases++
				cover = true
				buffer = buffer & (buffer -1)
				// continue
			}
		}
		if(cover){ coverFailedCases++}
	}
	oneNums := 0
	for i := 0; i < len(r); i++ {
		buffer := r[i]
		for buffer > 0 {
			oneNums++
			buffer &= (buffer - 1)
		}
	}

	if numOfOnesFromFailedCases == 0 {
		fitValue = 0
		return
	}
	if coverFailedCases < len(casesFailed) {
		fitValue = 0
		return
	}
	numOfOnesFromFailedCases = oneNums * len(casesFailed) - numOfOnesFromFailedCases
	// if numOfOnesFromFailedCases < len(casesFailed) {
	// 	fitValue = 0
	// 	return
	// }
	fitValue = float64(numOfOnesFromFailedCases) /
	math.Sqrt(
		float64(len(casesFailed)) * float64(numOfOnesFromFailedCases + numOfOnesFromPassCases))
	// fitValue = float64(numOfOnesFromFailedCases) / float64(oneNums * len(casesFailed)) / (   float64(numOfOnesFromPassCases) / float64(oneNums * len(casesSuccess)) + float64(numOfOnesFromFailedCases) / float64(oneNums * len(casesFailed))   )
	// fmt.Println(float64(numOfOnesFromFailedCases))
	//fitValue *= math.Sqrt(1 - math.Pow(float64(oneNums) / float64(size), 2)) * 10000
	fitValue *= math.Pow(0.02, float64(oneNums) / float64(30))
	// fmt.Println(fitValue)
	return
}

//parse string to generate []uint64
func stringToByteArray(s string, c *gaConfig, pass bool) (result []uint64) {
	fixsize := c.noes
	result = make([]uint64, 0)
	var buffer uint64
	var count = 0
	if fixsize % 64 != 0 {
		count = 64 - fixsize % 64
	}
	var i = 0;
	for _, b := range s {
		switch b {
		case 48:
			buffer = buffer << 1
			i++
			count++
		case 49:
			if pass {
				c.onesFromPass[i] += 1
			} else {
				c.onesFromFailed[i] += 1
			}
			i++
			buffer = (buffer << 1) | 1
			count++
		}
		if count > 0 && count % 64 == 0 {
			result = append(result, buffer)
			buffer = 0
			count = 0
		}
	}
	// if buffer%64 != 0 {
	// result = append(result, buffer)
	// }
	return result
}

//print out []uint64 with fix width
func displayByteArray(r *Record, fixed int, col []int) {
	fmt.Printf("Value: %f，genetic byte: ", r.fitvalue)
	ia := r.detail
	result := ""
	for _, i := range ia {
		fmt.Printf("%064s", strconv.FormatUint(i, 2))
		result = result + " " + strconv.FormatUint(i, 2)
	}
	fmt.Println()

	for i := 0; i < len(col); i++ {
		pos := col[i]
		if fixed % 64 != 0 {
			pos += 64 - fixed % 64
		}
		fmt.Println(" bit value: ", r.detail[pos / 64] & (1 << uint(63 - (pos % 64))))
	}
}

func isMatchErrorLine(r *Record, fixed int, errorLines []int) bool {

	found := false;
	for i := 0; i < len(errorLines) && !found; i++ {
		pos := errorLines[i]
		if fixed % 64 != 0 {
			pos += 64 - fixed % 64
		}
		found = (r.detail[pos / 64] & (1 << uint(63 - (pos % 64)))) > 0
	}
	// fmt.Println(" bit value: ", r.detail[pos/64]&(1<<uint(63-(pos%64))))
	return found
}

func main() {
	//parse the input
	flag.Parse()

	//init config from input file
	config1, err := initConfig(*dataFilePath)
	config = config1
	if err != nil {
		fmt.Println("Error")
	}
	// fmt.Println("Test Cases File loaded! config: ", config)
	// fmt.Println(strings.Repeat("*", 80))

	// //print the line info before sort
	for i := 0; i < len(config.compareValue); i++ {
		fmt.Println(config.compareValue[i], " ")
	}
	fmt.Println()


	//return

	var parentGroupSize = 500
	// var firstClassGroup = parentGroupSize * 4 / 10
	var vectorSize = config.noes
	var iterCountEachGeneration = parentGroupSize * 6 / 10 * 50
	fmt.Println("group size:", parentGroupSize)

	start := time.Now()
	var result []uint
	for i := 0; i < 1; i++ {
		result = gaCore(parentGroupSize, vectorSize, config, iterCountEachGeneration)
		fmt.Print("result=",result, "\n")
	}
	//for i, v := range result{
	//	fmt.Print(i, " : " , v)
	//}
	//result /= 30
	//fmt.Println("result: ", result)
	fmt.Println("Generating Random Parent Group time: ", time.Since(start))

}


func gaCore(parentGroupSize int, vectorSize int, config *gaConfig, iterCountEachGeneration int) []uint {
	//random init parentGroup
	heap := GAHeap{data: make([]Record, parentGroupSize), size: parentGroupSize}
	for i := 0; i < parentGroupSize; i++ {
		gene := randomParent(vectorSize)
		heap.insert(Record{gene, fitness(gene, vectorSize, config.casesPass, config.casesFailed)})
	}

	for i := 0; i < iterCountEachGeneration; i++ {
		father, mother := heap.randomPair()
		boy, girl := haveSex(father.detail, mother.detail, vectorSize)
		//check for boy
		heap.checkAndExchange(Record{boy, fitness(boy, vectorSize, config.casesPass, config.casesFailed)})
		//check for boy
		heap.checkAndExchange(Record{girl, fitness(girl, vectorSize, config.casesPass, config.casesFailed)})
	}

	//store all records from heap to array
	recordsAfterFound:= make([]Record, parentGroupSize)
	for i := parentGroupSize - 1; i >= 0; i-- {
		r := heap.getAndRemoveTop()
		displayByteArray(&r, vectorSize, config.lofs)
		//if isMatchErrorLine(&r, vectorSize, config.lofs) {
		//	recordsAfterFound = []Record{}
		//}
		recordsAfterFound[i] = r
		//recordsAfterFound = append(recordsAfterFound, r)
	}

	//store checking order for code line
	result := make([]lineInfo, 0)
	codeCoverate := make([]bool, vectorSize)
	//index := 0

	for _, r:= range recordsAfterFound{
		for i:= len(r.detail) - 1; i >= 0; i--{
			var offset uint = 0
			tmp := make(lines, 0)
			for offset < 64{
				if(1 << offset) & r.detail[i] > 0{
					lineNo := uint(vectorSize) - 1 - offset - uint(((len(r.detail) - 1 - i) << 6))
					if !codeCoverate[lineNo] {
						codeCoverate[lineNo] = true
						tmp = append(tmp, lineInfo{lineNo,config.compareValue[lineNo].value})
					}
				}
				offset++
			}
			sort.Sort(tmp)
			result = append(result, tmp...)
			//for j:= 0; j < len(tmp); j++{
			//	result[index] = tmp[j]
			//	index++
			//}
		}
		// displayByteArray(&r, vectorSize, config.lofs)
	}

	remainRecords := make(lines, 0)
	for i, v := range codeCoverate{
		if !v{
			remainRecords = append(remainRecords, config.compareValue[i])
		}
	}
	sort.Sort(remainRecords)
	//fmt.Println(len(result))
	result = append(result, remainRecords...)
	lines := make([]uint, vectorSize)
	for i:=0; i < len(result); i++{
		lines[i] = result[i].lineNO
	}
	return lines
	//fmt.Println(result)




	////calculate the ones need search before get the right match
	//ss := vectorSize >> 6
	//if vectorSize != vectorSize << 6 {
	//	ss++
	//}
	//if !isMatchErrorLine(&recordsAfterFound[0], vectorSize, config.lofs) {
	//	fmt.Println("not found")
	//	return float32(vectorSize);
	//}
	//
	//ones := make([]uint64, ss)
	//for i := 0; i < len(recordsAfterFound); i++ {
	//	for j := 0; j < ss; j++ {
	//		ones[j] |= recordsAfterFound[i].detail[j]
	//	}
	//	//displayByteArray(&recordsAfterFound[i], vectorSize, config.lofs)
	//}
	//
	//sum := 0
	//for i := 0; i < ss; i++ {
	//	for ones[i] > 0 {
	//		sum++
	//		ones[i] &= ones[i] - 1
	//	}
	//}
	//
	//fmt.Println("ones: ", sum, " / ", vectorSize)
	//return result
}
